package com.s8.skipList;

public class SkipList {

	public static void main(String[] args) {
		SkipList skipList = new SkipList();
		skipList.insert(1);	
		skipList.insert(5);	

		skipList.printAll();
		
		System.out.println("-----------");
		
		skipList.printAll();
	}

	// 目前采用 二分之一 的策略
	private static final float SKIPLIST_P = 0.5f;
	private static final int MAX_LEVEL = 16;

	// 目前到达的最高层级。 [1, MAX_LEVEL]
	private int levelCount = 1;

	private Node head = new Node(); // 带头链表,不存储数据

	public Node find(int value) {
		Node p = head;
		for (int i = this.levelCount - 1; i >= 0; --i) {
			while (p.forwards[i] != null && p.forwards[i].data < value) {
				p = p.forwards[i];
			}
		}

		if (p.forwards[0] != null && p.forwards[0].data == value) {
			return p.forwards[0];
		} else {
			return null;
		}
	}

	public void insert(int value) {
		int level = this.randomLevel();
		Node newNode = new Node();
		newNode.data = value;
		newNode.maxLevel = level;
		// 对应 [0, level - 1]
		Node update[] = new Node[level];
		for (int i = 0; i < level; ++i) {
			update[i] = head;
		}

		// record every level largest value which smaller than insert value in
		// update[]
		Node p = head;
		for (int i = level - 1; i >= 0; --i) {
			while (p.forwards[i] != null && p.forwards[i].data < value) {
				p = p.forwards[i];
			}
			update[i] = p;// use update save node in search path
		}

		// in search path node next node become new node forwords(next)
		for (int i = 0; i < level; ++i) {
			newNode.forwards[i] = update[i].forwards[i];
			update[i].forwards[i] = newNode;
		}

		// update node hight
		if (levelCount < level) {
			levelCount = level;
		}
	}

	public void delete(int value) {
		Node[] update = new Node[levelCount];
		Node p = head;
	}

	public void printAll() {
		Node p = head;
		while (p.forwards[0] != null) {
			System.out.print(p.forwards[0] + " ");
			p = p.forwards[0];
		}
		System.out.println();
	}

	// 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
	// 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
	// 该 randomLevel 方法会随机生成 [1, MAX_LEVEL] 之间的数，且 ：
	// 50%的概率返回 1
	// 25%的概率返回 2
	// 12.5%的概率返回 3 ...
	
	/**
	 *  [1, MAX_LEVEL]
	 */
	private int randomLevel() {
		int level = 1;
		while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
			level++;
		return level;
	}

	public class Node {
		private int data = -1;
		private Node forwards[] = new Node[MAX_LEVEL];
		// [1, MAX_LEVEL]
		private int maxLevel = 0;

		@Override
		public String toString() {
			return "{data: " + this.data + ", maxLevel: " + this.maxLevel + "}";
		}
	}
}
